# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2022/1/18
# @File : 快速排序.py

import random
class Solution:
    def MySort(self , arr ):
        def quicksort(nums,l,r):
            if l >= r: return
            pivot = random.randint(l,r)
            nums[pivot],nums[l] = nums[l],nums[pivot]

            i = l

            for j in range(l+1,r+1):
                if nums[j] < nums[l]:
                    i += 1
                    nums[i],nums[j] = nums[j],nums[i]
            nums[i],nums[l] = nums[l],nums[i]

            quicksort(nums,i+1,r)
            quicksort(nums,l,i-1)

        quicksort(arr,0,len(arr)-1)
        return arr
"""
def quick_sort(nums):

    if(len(nums) <=1): return nums;

    privot =nums[len(nums)//2]
    left =[x for x in nums if x < privot]
    mid =[x for x in nums if x == privot]
    right =[x for x in nums if x> privot]
    #print (" ".join(list(map(str, left))) +","+ str(mid[0]) +","+" ".join(list(map(str, right))) )
    return quick_sort(left) +mid + quick_sort(right)

作者：jijeng
链接：https://www.acwing.com/solution/content/5599/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""